perm filename CRE.DOC[2,BGB] blob
sn#032376 filedate 1973-04-09 generic text, type T, neo UTF8
COMMENT ⊗ VALID 00027 PAGES
RECORD PAGE DESCRIPTION
00001 00001
00004 00002 SAILON NUMBER 71. DRAFT CRE MANUAL.
00006 00003 INTRODUCTION.
00008 00004 I. A. DATA STRUCTURE.
00011 00005 TYPES OF NODES.
00015 00006 CRE SUB-STRUCTURES:
00016 00007 VECTOR/ARC/VERTEX NODE FORMAT.
00020 00008 THE VECTOR/ARC/VERTEX NODE.
00023 00009 THE EDGE NODE FORMAT.
00026 00010 FACE NODE FORMAT.
00030 00011 IMAGE NODE FORMAT.
00034 00012 THE ALGORITHM.
00036 00013 THRESHOLDING.
00038 00014 CONTOURING.
00041 00015 PERFORMANCE
00042 00016 ALPHABETIC SUMMARY OF TELETYPE COMMANDS.
00044 00017 SUMMARY OF BASIC COMMANDS.
00045 00018 TELEVISION PICTURE IO COMMANDS.
00046 00019 LINK FOLLOWING COMMANDS & NODE CONTENTS DISPLAY.
00049 00020 DISPLAY WINDOW SCROLLING COMMANDS.
00051 00021 OPERATIONAL SUMMARY OF CRE TELETYPE COMMANDS.
00052 00022 CART CONTROL COMMANDS & OPERATING THE CART.
00055 00023 II. FILE FORMATS.
00058 00024 V. SAIL INTERFACING.
00061 00025 EDITORIAL REMARKS.
00065 00026 CODE DOCUMENTATION.
00068 00027 REFERENCES.
00069 ENDMK
⊗;
SAILON NUMBER 71. DRAFT CRE MANUAL.
STANFORD ARTIFICIAL INTELLIGENCE LABORATORY JANUARY 1973.
OPERATING NOTE NUMBER 71.
- - - DRAFT - - -
Contour-Region-Edge Image Representation.
Bruce g. Baumgart
ABSTRACT:
A contour-region-edge, CRE, image representation is stated
and an algorithm for converting a digital television image into this
format is explained. An implementation of the algorithm is the main
routine of a program called Cart's Eye, CRE; auxiliary routines
provide manual cart control, TV camera input, image display, and
Xerox Graphics Printer output. Potential application of CRE as a step
in object perception is discussed.
CONTENTS:
I.
A. DATA STRUCTURE.
B. THE ALGORITHM.
C. PERFORMANCE.
II.
A. TELETYPE COMMANDS.
B. FILE FORMATS.
C. SAIL INTERFACING.
D. LISP INTERFACING.
III.
A. EDITORIAL REMARKS.
B. CODE DOCUMENTATION.
C. APPENDICES.
This research was supported by the Advanced Research Projects Agency
of the Office of the Secretary of Defense under contract SD-183.
INTRODUCTION.
CRE is a solution to the problem of finding all the
photometric edges in a television picture and the regions bounded by
those edges; this is done by building the edges and regions on top of
a very literal intensity contour map. Edges are formed where contour
lines run close together and regions are closed by following contour
lines across "flatlands" until they return to their edges. Also CRE
links regions and edges of one image with corresponding regions and
edges of the previous image.
The process is automatic and is intended to run without human
intervention. Furthermore, the process is "bottom up"; there are no
significant inputs other than the given television images. The CRE
design goal is to provide video image input data in a basic list
structured form appropriate for my geometric editor, GEOMED; other
aspects of the vision problem such as 3D perception, object
recognition, wide angle comparison, photometric normalization, and so
on are not attempted in CRE.
I. A. DATA STRUCTURE.
Contour-Region-Edge or CRE, is a combination of ideas; the
two principle ideas being that of an elevation contour map and that
of a political map. On a contour map of an island fully surrounded by
ocean, no two contour lines every cross and all the contour lines
close. Consequently, the loops of elevation contours enclose
regions; and these regions overlap in a nested fashion forming a tree
data structure. On political maps, ignoring for the moment geographic
pathologies such as Vietnam and the Vatican; no two states ever
overlap, the states are bounded by borders, and the regions within
the borders are simply connected.
One idea that is emphatically not in CRE is that of a
schematic line drawing. Although the CRE output can be viewed as a
collection of lines on a display screen, people expecting a line
drawing rendition of the given television picture will be
disappointed. A CRE picture is a simple translation of the
photometry, geometry and topology of the orginal video image. Whereas
the typical line drawing from a human illustrator is a representation
of the scene without photometric information.
The data structure to be discussed is implemented as small
blocks of words containing pointers and data in the fashion usual to
graphics and simulation; an introduction to this technology can be
found in Knuth [1]. The language of implementation is PDP-10 machine
code via the FAIL assembler. The direct explanation of CRE structure
will be presented in three parts: first, the several kinds of nodes
will be briefly explained; second, the sub-structures such as rings,
trees and lists will be discribed; and third, the detailed node
formats will be given.
TYPES OF NODES.
The are several types of CRE nodes: Vector, Arc, Vertex,
Polygon, Face, Edge, Image, Level, Film, Empty and Extra. At the
very top of all the structure is the film node, the film node is
unique and serves as an OBLIST from which all other nodes may be
reached. The film node embodies the idea of a piece of celluloid
film or a length of magnetic video tape; in the abstract, a sequence
of images taken by the same camera of the same scene with only a
small amount of action or difference between images.
An image node represents the familair two dimensional idea of
a photograph or an oil painting. An image node has two immediate sub
structures that may exist simultaneously; there is the intensity
contour image composed of level and polygon nodes, and there is the
winged edge image composed of faces and edges.
The level node represents a photometrically binary image that
results from thresholding a gray scale image. Polygon nodes express
the notion of never intersecting contour lines each of which always
closes upon itself. Contour lines are approximated by a ring of
vectors hence the term "polygon".
CRUDE DIAGRAM OF NODE "IMMEDIACY" BY TYPE.
FILM →→→ Empties
↓
↓
↓
←←←←← IMAGES →→→→→→
↓ ↓
↓ ↓
↓ ↓
FACES & EDGES LEVELS & POLYGONS →→→ extras.
↓ ↓
↓ ↓
↓ ↓
VECTORS, VERTICES & ARCS →→→ extras.
The face, edge and vertex nodes are the three elements
necessary for representing the idea of a mosaic or 2D tesselation,
that is a picture made of little pieces placed tightly side by side
to completely cover the image wihtout overlapping.
Empty nodes and Extra nodes are artifacts of the fixed block
size dynamic storage allocation mechanism used in CRE. Entities are
made by taking blocks from an AVAIL list of empty nodes and entities
are killed by returning the block to the AVAIL list; there is no
garbage collector, but there is a space compactor called SHRINK.
Extra nodes are used to provide additional space for the ARC and
POLYGON nodes; so that ARC and POLYGON are double sized nodes.
CRE SUB-STRUCTURES:
SEVEN RINGS.
1. Image Ring of a Film.
2. Level Ring of an Image.
3. Polygon Ring of a Level.
4. Vector Ring of a Polygon.
5. Arc Ring of a Polygon.
6. Face Ring of an Image.
7. Edge Ring of an Image.
THREE PAIRS.
1. Arc↔Vector Pairs.
2. Vector↔Vector Radial Pairs.
3. Arc↔Arc Radial Pairs.
TWO TREES.
1. The Tree of Rings.
2. The Polygon Tree.
TWO LISTS.
1. Time Lists.
2. The empty node list.
ONE EULER GRAPH.
1. Winged Edge Structure - Face, Edge, Vertex.
VECTOR/ARC/VERTEX NODE FORMAT.
_____________________________________________
word | CW | CCW |
0 | vector ring |
_____|___________________|___________________|
word | ROW | COL |
1 | ∂ 0000.00 | ∂ 0000.00 |
_____|___________________|___________________|
word | TYPE | RELOC |
2 | ∂ 1 | ∂ 303 313 |
_____|___________________|___________________|
word | | |
3 | ENDO | EXO |
_____|___________________|___________________|
word | | |
4 | ARC | PED |
_____|___________________|___________________|
word | | |
5 | ∂ CNTRST | PGON |
_____|___________________|___________________|
word | | |
6 | NTIME | PTIME |
_____|___________________|___________________|
POLYGON NODE FORMAT.
_____________________________________________
word | CW | CCW |
0 | polygon ring |
_____|___________________|___________________|
word | DAD | SON |
1 | level | 1st vector |
_____|___________________|___________________|
word | TYPE | RELOC |
2 | 10 | 333 233 |
_____|___________________|___________________|
word | | |
3 | ENDO | EXO |
_____|___________________|___________________|
word | | |
4 | ARC | NCNT |
_____|___________________|___________________|
word | | |
5 | NGON | PGON |
_____|___________________|___________________|
word | | |
6 | NTIME | PTIME |
_____|___________________|___________________|
THE VECTOR/ARC/VERTEX NODE.
The most numerous kind of node is the VECTOR/ARC/VERTEX,
which for informal discussion will be called a VERTEX.
Vertices carry the fundamental geometric datum of an image locus. The
image locus is stored in halfword positions named ROW and COL, which
contain the row and column of a point in units 1/64 of a pixel. A
"pixel" is a "picture element".
Vertices when used as vectors or arcs also carry the fundamental
photometric datum of edge contrast. Fundamental data is that data
which comes almost irectly from the video image and is used to
compute other data such face area or region gradient.
Vertices always belong to a polygon node, a pointer to the polygon of
each vertex is stored in the link named PGON; as members of a polygon
the vertices form a perimeter or loop which is always connected so
that each vertex has a neighboring vertex in the clockwise and in the
counter clockwise directions about the polygon's perimeter. There
perimeter pointers re stored in the link positions named CW and CCW.
The links named NTIME and PTIME appear in all nodes except
the film node; these links connect corresponding parts of a given
image with parts of its immediate predecessor image and with parts of
its immediate successor image. Time links implement the notion of a
film where each frame differs but little from its neighboring frames
along the film.
THE EDGE NODE FORMAT.
_____________________________________________
word | NCW clockwise NCW |
0 | wings |
_____|___________________|___________________|
word | NCCW counter PCCW |
1 | clockwise wings |
_____|___________________|___________________|
word | TYPE | RELOC |
2 | ∂ 02 | ∂ 400 000 |
_____|___________________|___________________|
word | | |
3 | NFACE | PFACE |
_____|___________________|___________________|
word | edge-ring |
4 | NED | PED |
_____|___________________|___________________|
word | | |
5 | NVT | PVT |
_____|___________________|___________________|
word | | |
6 | NTIME | PTIME |
_____|___________________|___________________|
WINGED EDGE MANDALA:
\ /
nccw \ / pcw
\ /
⊗ pvt
|
nface E pface
|
nvt ⊗
/ \
ncw / \ pccw
/ \
FACE NODE FORMAT.
_____________________________________________
word | CW | CCW |
0 | vector ring |
_____|___________________|___________________|
word | DAD | |
1 | image | |
_____|___________________|___________________|
word | TYPE | RELOC |
2 | ∂ 04 | ∂ 023 103 |
_____|___________________|___________________|
word | face-ring |
3 | NFACE | PFACE |
_____|___________________|___________________|
word | | |
4 | | PED |
_____|___________________|___________________|
word | | |
5 | ∂ PERIM | ∂ AREA |
_____|___________________|___________________|
word | | |
6 | NTIME | PTIME |
_____|___________________|___________________|
FILM NODE FORMAT.
_____________________________________________
word | | |
0 | | core size |
_____|___________________|___________________|
word | | SON |
1 | | image |
_____|___________________|___________________|
word | TYPE | RELOC |
2 | ∂ 100 | 011 000 |
_____|___________________|___________________|
word | | |
3 | | |
_____|___________________|___________________|
word | | |
4 | | |
_____|___________________|___________________|
word | | |
5 | | |
_____|___________________|___________________|
word | | |
6 | | |
_____|___________________|___________________|
IMAGE NODE FORMAT.
_____________________________________________
word | CW | CCW |
0 | image ring |
_____|___________________|___________________|
word | DAD | SON |
1 | film | level |
_____|___________________|___________________|
word | TYPE | RELOC |
2 | 40 | 333 333 |
_____|___________________|___________________|
word | face ring |
3 | NFACE | PFACE |
_____|___________________|___________________|
word | edge ring |
4 | NED | PED |
_____|___________________|___________________|
word | vertex ring |
5 | NVT | PVT |
_____|___________________|___________________|
word | | |
6 | NTIME | PTIME |
_____|___________________|___________________|
LEVEL NODE FORMAT.
_____________________________________________
word | CW | CCW |
0 | level ring |
_____|___________________|___________________|
word | DAD | SON |
1 | image | polygon |
_____|___________________|___________________|
word | TYPE | RELOC |
2 | ∂ 20 | ∂ 330 003 |
_____|___________________|___________________|
word | | |
3 | | |
_____|___________________|___________________|
word | | |
4 | | |
_____|___________________|___________________|
word | | |
5 | | |
_____|___________________|___________________|
word | | |
6 | NTIME | PTIME |
_____|___________________|___________________|
THE ALGORITHM.
In the large, CRE consists of five steps: thresholding,
contouring, smoothing, bundling and comparing. The first four steps
perform conversions between five kinds of images: 6-bit raster
image, 1-bit raster image, vector intensity contour image, arc
contour image, and winged edge image. The final step, comparing,
joins an image to a film of images by linking the parts of the
cuurent image to the parts of the previous image that compare nearly
equal.
MAJOR OPERATION. OPERAND. RESULT.
1. THRESHOLDING: 6-BIT-IMAGE 1-BIT-IMAGES.
2. CONTOURING: 1-BIT-IMAGES VIC-IMAGE.
3. SMOOTHING: VIC-IMAGE ARC-IMAGE.
4. BUNDLING: ARC-IMAGE WINGED-IMAGE.
5. COMPARING: IMAGE & FILM FILM.
THRESHOLDING.
Thresholding, the first and easiest step, consists of two subroutines:
1. THRESH: CUT,TVBUF → PAC
2. PACXOR: PAC → HSEG,VSEG
The subroutine THRESH takes an integer argument, 0 < CUT ≤ 63, and
for each pixel in the TVBUF with value equal to or greater than the
cut THRESH sets a bit in PAC. PAC (picture accumulator) is a bit
array of 216 rows by 288 columns which takes 1728 words in the TVSEG.
The subroutine PACXOR first copies the PAC into two slightly larger
bit arrays named HSEG and VSEG, then it exclusive OR's the PAC,
properly displaced one row or one column, into HSEG and VSEG to
compute the horizontal and vertical border bits of blobs in the PAC.
CONTOURING.
Contouring, the next major step, converts the bit arrays HSEG
and VSEG into a node-link data structure that represents an equal
intensity level contour map. Of such contouring, there be two minor
steps: one, that of tracing the contour as a ring of vectors to form
a polygon; and two, that of placing the polygon in the contour tree
data structure.
Although the notion of a contour
map is familiar to everyone as a piece of paper from the Geodetic
Survey Office; implementing the notion into a data structure becomes
a magical mystery tour. Two of the contouring mysteries to be
discussed are jaggies and nesting. The jaggies problem involves doing
something to a rectilinear quantized set of segments, to make its
linear nature more evident. The jaggies solution in CRE is called
the dekinking, and merely involves vernier positioning the
right-turns as will be explained below.
A JAGGY ILLUSTRATED.
___
|___
|____
|___
|___
The nesting problem involves comparing two polygons and deciding
whether one is within the other; although easy in an isolated case,
solving alot of nesting becomes very expensive in compute time or in
memory space. The nesting solution in CRE is a fast big memory one
involving a 62K array, called the SKYSEG.
SMOOTHING.
BUNDLING.
PERFORMANCE
ALPHABETIC SUMMARY OF TELETYPE COMMANDS.
"A" Toggle Arc Make flag.
"B" Drive the cart backwards.
"C" Cut intensity level.
"D" Toggle baby polygon delete flag.
"E" Select Edge Display.
"F" Drive the cart forwards.
"G"
"H" Display histogram.
"I" Input TV picture from a disk file.
"J" Contour TV image at levels 6% from ends of histogram.
"K" Toggle Krakauer flag.
"L" Set cart steering to hard left position.
"αL" Pan cart camera to the left.
"M"
"N" Next image.
"O" Output TV file.
"αO" Output CRE file.
"P" Plot file output to disk the current III display buffer.
"Q" Contour TV image at equally spaced levels.
"R" Set cart steering to hard right position.
"αR" Pan cart camera to the right.
"S" Select camera number.
"T" Take 4-bit television picture.
"αT" Take 6-bit television picture.
"U" Toggle KILVIC enable flag.
"V" Enter cart diagnostic sub command mode.
"W" Alter Arc width table.
"X" XGP output.
"Y" Display arc-contour.
"αY" Display both-contour.
"βY" Display vector-contour.
"εY" Display vector contour without dekinking.
"Z" Zero data structure.
"αZ" Zoom Reset to initial display position.
SUMMARY OF BASIC COMMANDS.
"T" Take a 4-bit television picture.
"H" Display histogram.
"Q" Make CRE image, from three intensity cuts.
"C 00" Make CRE image by thresholding at 00.
"O" Output television picture.
"αO" Output CRE file.
"X" Output video to XGP.
TELEVISION PICTURE IO COMMANDS.
"T" Take a 4-bit video image from camera.
"αT" Take a 6-bit video image from camera.
"S" Select television camera.
"O" Output video image file to disk.
"I" Input video image file from disk.
LINK FOLLOWING COMMANDS & NODE CONTENTS DISPLAY.
These 14 commands allow detailed inspection of the CRE data
structure by showing the contents of a node. Data halfwords of a node
are displayed in octal; link halfwords are displayed
prefixed with a letter indicating the type of node being pointed at;
a zero link is displayed as "NIL".
The FILM node, which is the root of the whole data structure is
fetched and displayed by the "+" command. From the Film, the ">"
command can be used to get SON(FILM) which is always the first image,
and ">" command of an image will get a level and ">" of a level will
get a polygon. Now vectors, polygons, edges and faces are intensified
when their contents are being displayed. The exit command is "!",
which leaves the screen less cluttered.
NODE CONTENTS DISPLAY
INITIATION & TERMINATION COMMANDS.
"+" Fetch Film Node.
"!" Flush diagonostic node display.
WORD NODE FETCH
POSITION COMMAND NAMES OF LINKS AT THIS WORD.
0. "," "." CW,,CCW
1. "<" ">" DAD,,SON
2. There is never a link at this word.
3. "↓" "↑" NFACE,,PFACE or ENDO,,EXO
4. "≤" "≥" NED,,PED or ARC,,PED
5. "←" "→" NVT,,PVT or NGON,,PGON
6. "⊂" "⊃" NTIME,,PTIME
DISPLAY WINDOW SCROLLING COMMANDS.
; MOVE CAMERA LEFT.
: MOVE CAMERA RIGHT.
( MOVE CAMERA DOWN.
) MOVE CAMERA UP.
- SHRINK IMAGE - ZOOM OUT.
* MAGNIFY IMAGE - ZOOM IN.
αZ RESET SCROLL VALUES.
/ HALVE STRENGTH OF SCROLLING DELTA.
\ DOUBLE STRENGTH OF SCROLLING DELTA.
DISPLAY MODES.
"Y" DISPLAY ARC POLYGONS ONLY.
"βY" DISPLAY VECTOR POLYGONS ONLY.
(which usually do not exist unless the "U" command
prevented their being deleted after being used.)
"αY" DISPLAY BOTH ARC & VECTOR POLYGONS.
"εY" DISPLAY VECTOR POLYGONS WITHOUT DEKINKING.
IMAGE OUTPUT COMMANDS.
"X" Output video image on Xerox Graphics Printer.
"P" Output III plot file to disk.
OPERATIONAL SUMMARY OF CRE TELETYPE COMMANDS.
INPUT/OUTPUT.
CART-CONTROL.
DISPLAY-CONTROL.
CONTOURING.
"C" cut at level.
"Q" equally spaced contours.
"J" Make two contour with respect to per centage from
ends of histogram.
"Q" - 3 CUTS: 20, 40, 60.
"αQ" - 7 CUTS: 10, 20, 30, 40, 50, 60, 70.
"βQ" - 8 CUTS: 04, 14, 24, 34, 44, 54, 64, 74.
"εQ" - 15 CUTS: 04,10,14,20,24,30,34,40,44,50,54,60,64,70,74.
CART CONTROL COMMANDS & OPERATING THE CART.
There are seven cart commands: drive forwards, drive
backwards, turn left, turn right, pan camera left, pan camera right
and halt:
"F" Drive Cart Forwards for one minute.
"B" Drive Cart Backwards for one minute.
"L" Turn steering wheels hard to left.
"R" Turn steering wheels hard to right.
"αL" Pan camera to the left for 10 seconds.
"αR" Pan camera to the right for 10 seconds.
" " Halt and continue spacewar job on PDP-6.
"0" Halt and continue spacewar job on PDP-6.
carriage return - Halt and stop spacewar job on PDP-6.
First and most important is understanding how to stop the cart. The
teletype halt command is " ", spacebar, or "0"; also any character
other than "F", "B", "L", or "R" will stop the cart. Cart commands
are passed first from a teletype to the PDP-10, then to the PDP-6,
then over a citizens band, 27.045 megahertz, radio link to the cart
control logic; and so when communications are lacking between
entities in the chain of command the lower entities times out and
causes the cart to halt. The cart control logic times out in a fifth
of a second if it does not hear from the PDP-6; the PDP-6 times out
in less than a minute if it has not heard from the PDP-10; the PDP-6
also stops broadcasting cart commands if it detects the death of the
PDP-10; the PDP-10 job times out after 5 minutes of not hearing
from the teletype and kills the PDP-6 spacewar job.
II. FILE FORMATS.
A. Television Image Format.
B. Region/Edge Image Format.
A. Television Image Format.
The standard Cart's Eye television image is
216 rows of 288 columns of 4 bits per pixel.
B. Contour/Region/Edge Image Format.
The image format, CRE, is essentially a core dump
of CRE's internal node/link data structure. There are eight kinds
of nodes and the nodes are fixed sized at six words per node.
From the top, the first node of a file is always a "FILM" node.
The head of a film node points to a ring of "IMAGE" nodes.
The head of an image node points to a ring of "LEVEL" nodes.
The head of a level node points to a ring of "POLYGON" nodes.
The head of a polygon node points to a ring of "EDGE" nodes.
And edge nodes do not have a head pointer. Which is equivalent to
saying that a file contains a film, a film is composed of images, an
image is composed of levels, a level is composed of polygons and a
polygon is composed of edges.
Now the detailed explanation will proceed bottom-up, starting
with the most numerous edge nodes.
File names are accepted in the usual DEC format of name, dot,
extension, left square bracket, project, comma, programmer, right
square bracket, carriage return line feed. Where the filename is from
one to six characters; and the extension project and programmer are
from one to three characters. Everything but the filename is
optional.
V. SAIL INTERFACING.
It should be possible to embed the CRE machine code under a
SAIL core image; however I do not intend to do this work. For the
present, the CRE interface to SAIL is only realized via a disk file
transfer of the data structures. A CRE file may be read into an
integer array in binary mode as illustrated below.
The first word of a CRE file is the first word of the film
node which contains the size of the file in words. The film node has
address 0; the next node has address 7; and so on in multiplies of
seven. There are no empty nodes in a CRE file. The following SAIL
program will read in a CRE file named X:
COMMENT EXAMPLE OF SAIL INPUT OF A CRE FILE;
BEGIN "TEST"
INTEGER SIZE;
OPEN(1,"DSK",8,3,0,0,0,0);
LOOKUP(1,"X.CRE",0);
SIZE ← WORDIN(1);
BEGIN
INTEGER ARRAY NODE[0:SIZE];
ARRYIN(1,NODE[1],SIZE-1);
RELEASE(1);
"MAIN PROGRAM.";
END;
END;
After the NODE array is loaded, CRE links and data may be accessed by
their document names in a reasonible node-link notation using macros
like the following:
DEFINE CW(Q) = "(NODE[Q] LSH -18)";
DEFINE CCW(Q) = "(NODE[Q] LAND '777777)";
DEFINE DAD(Q) = "(NODE[Q+1] LSH -18)";
DEFINE SON(Q) = "(NODE[Q+1] LAND '777777)";
So that the first vertex of the first polygon of the first level of
the first image of the film can be obtained:
INTEGER FILM,IMAGE,LEVEL,POLYGON,VERTEX;
FILM ← NODE[0];
LEVEL ← SON(FILM);
POLYGON ← SON(LEVEL);
VERTEX ← SON(POLYGON);
The user may note that SAIL will compile three or more instructuions
for what is known as a PDP-10 halfword operation; also if the user
converts the CRE nodes and links into LEAP items and associations
then an overhead of from ten to one hundred instructions per
"halfword operation" will be incurred.
EDITORIAL REMARKS.
1.
The version of CRE discussed in this document is known to
me as the third, or the version of Christmas-72. CAREYE-I of '68 and
'69 was embedded in LISP and contained thresholding, bit raster
operations, and a polygon trace routine. CAREYE-II was embedded in
SAIL, and in early forms even used LEAP. Both CAREYE-I and CAREYE-II
were built around the notion of "windowing". CAREYE-IV, of
Thanksgiving-72 was was scan line oriented.
3.
It is my impression that all the so called "scientific" ideas
in CRE have appeared elsewhere. In particular, I was aware of and
kind of liked the work of Krakauer, Zahn, and Mc Cormick's
ILLAIC-III. Also, I was aware of and disliked the work of Pingle and
Hueckel. I wish to acknowledge all these people from whom I have
borrowed ideas, both positive and negative. On the other hand, I
alone wrote and developed all the code in CRE.
6. ANTI VARIABLE WINDOWING.
The requirement that a vision program must handle variable
sized windows is a severe limitation which has bogged
down potentially good image processing ideas in a morass of word
packing, array binding, window splicing, and cost optimization;
not directly relevant to image processing.
7. ANTI VISUAL FEEDBACK ON THE TACTICAL LEVEL.
A vision system must have feedback, accomodation, prediction,
verification, and higher level knowledge. The pursuit of this visual
feedback format seems to lead one to work solely on building a forest
without worrying about how to build a tree.
8. ANTI HIGHER LEVEL LANGUAGES & PRO MACHINE CODE.
Another banal truism in AI is that a higher level language
allows rapid implementation and experimental change of poorly
understood algorithms.
CODE DOCUMENTATION.
The CRE code uses additional PDP-10 mnemonics for the sake of
pronouciation and brevity. The mnemonics stem from ancient PDP-1
nomenclature; in the PDP-10 the left half word is the instruction
part and the right half word is the address part. The codes CAR and
CDR are traditional LISP names, derived from IBM-709 nomenclature;
CAR and CDR are appropriate PDP-6/10 op codes because according to
Kotok,the machine was designed to facilitate LISP.
HLR LIP Load Instruction Part.
HRR LAP Load Address Part.
HRLM DIP Deposit in Instruction Part.
HRRM DAP Deposit in Instruction Part.
HRRZS ZIP Zero Instruction Part.
HLLZS ZAP Zero Address Part.
HRROS WIP W'ones to Instruction Part.
HLLOS WAP W'ones to Address Part.
HLRZ CAR Contents Address Register.
HRLI LIPI Load Instruction Part Immediate.
HRRI LAPI Load Address Part Immediate.
HRLZM DIPZ Deposit into Instruction Part with Zeroes.
HRRZ CDR Contents Decrement Register.
MOVEI LACI Load Accumulator Immediate.
MOVSI SLACI Swap Load Accumulator Immediate.
HRRZM DAPZ Deposit into Address Part with Zeroes.
MOVE LAC Load Accumulator.
MOVN LACN Load Accumulator Negative.
MOVM LACM Load Accumulator Magnitude.
MOVS SLAC Swap Load Accumulator.
MOVEM DAC Deposit Accumulator into memory.
MOVNM DACN Deposit Accumulator Negative.
MOVMM DACM Deposit Accumulator Magnitude.
MOVSM SDAC Swap Deposit Accumulator.
HLRE NIP Number from Instruction Part.
HRRE NAP Number from Address Part.
HRREI NIM Number Immediate.
JRST GO Load program counter immediate.
REFERENCES.
KNUTH
KRAKAUER
GEOMED SAILON
WINGED EDGE PAPER